<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Strongly Connected Components Kosaraju's Algorithm Graph Algorithm</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="strongly-connected-components-kosarajus-algorithm-graph-algorithm">Strongly Connected Components Kosaraju's Algorithm Graph Algorithm</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=RpgcYiky7uw&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=8">https://www.youtube.com/watch?v=RpgcYiky7uw&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=8</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/StronglyConnectedComponent.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/StronglyConnectedComponent.java</a></li>
</ul>
<p>查找有向图中所有的强连通域，强连通域的定义是， 域内部所有的节点都可以访问到其它节点, 如下图所示，有4个强连通域</p>
<ol>
<li>IHGJ</li>
<li>K</li>
<li>ABC</li>
<li>DEF</li>
</ol>
<p>算法需要dfs遍历两次</p>
<ol>
<li>第一次遍历dfs, 得到按照遍历时间排序的stack1, 这个过程和前面拓扑排序dfs很像</li>
</ol>
<p><img src="file:///e:\gitee\leetcode\graph\pics\connect1.png" alt="connect1.png"></p>
<ol start="2">
<li>将图中的所有边做反向，然后根据stack1的顺序，再次做dfs遍历。</li>
</ol>
<p><img src="file:///e:\gitee\leetcode\graph\pics\connect2.png" alt="connect2.png"></p>
<p>最终得到所有的强连通域</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\connect3.png" alt="connect3.png"></p>
<p>时间复杂度 第一次遍历 O(E+V) 第二次遍历 O(E+V), 最后还是O(E+V)</p>
<p>空间复杂度 O(V)</p>
<p>关于这个算法的证明也很巧妙， 还是看视频吧。</p>
<pre><code class="language-java"><div><span class="hljs-keyword">package</span> com.interview.graph;

<span class="hljs-keyword">import</span> java.util.ArrayDeque;
<span class="hljs-keyword">import</span> java.util.ArrayList;
<span class="hljs-keyword">import</span> java.util.Deque;
<span class="hljs-keyword">import</span> java.util.HashSet;
<span class="hljs-keyword">import</span> java.util.List;
<span class="hljs-keyword">import</span> java.util.Set;

<span class="hljs-comment">/**
 * Date 10/01/2014
 * <span class="hljs-doctag">@author</span> Tushar Roy
 *
 * Given a directed graph, find all strongly connected components in this graph.
 * We are going to use Kosaraju's algorithm to find strongly connected component.
 *
 * Algorithm
 * Create a order of vertices by finish time in decreasing order.
 * Reverse the graph
 * Do a DFS on reverse graph by finish time of vertex and created strongly connected
 * components.
 *
 * Runtime complexity - O(V + E)
 * Space complexity - O(V)
 *
 * References
 * https://en.wikipedia.org/wiki/Strongly_connected_component
 * http://www.geeksforgeeks.org/strongly-connected-components/
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">StronglyConnectedComponent</span> </span>{

    <span class="hljs-keyword">public</span> List&lt;Set&lt;Vertex&lt;Integer&gt;&gt;&gt; scc(Graph&lt;Integer&gt; graph) {

        <span class="hljs-comment">//it holds vertices by finish time in reverse order.</span>
        Deque&lt;Vertex&lt;Integer&gt;&gt; stack = <span class="hljs-keyword">new</span> ArrayDeque&lt;&gt;();
        <span class="hljs-comment">//holds visited vertices for DFS.</span>
        Set&lt;Vertex&lt;Integer&gt;&gt; visited = <span class="hljs-keyword">new</span> HashSet&lt;&gt;();

        <span class="hljs-comment">//populate stack with vertices with vertex finishing last at the top.</span>
        <span class="hljs-keyword">for</span> (Vertex&lt;Integer&gt; vertex : graph.getAllVertex()) {
            <span class="hljs-keyword">if</span> (visited.contains(vertex)) {
                <span class="hljs-keyword">continue</span>;
            }
            DFSUtil(vertex, visited, stack);
        }

        <span class="hljs-comment">//reverse the graph.</span>
        Graph&lt;Integer&gt; reverseGraph = reverseGraph(graph);

        <span class="hljs-comment">//Do a DFS based off vertex finish time in decreasing order on reverse graph..</span>
        visited.clear();
        List&lt;Set&lt;Vertex&lt;Integer&gt;&gt;&gt; result = <span class="hljs-keyword">new</span> ArrayList&lt;&gt;();
        <span class="hljs-keyword">while</span> (!stack.isEmpty()) {
            Vertex&lt;Integer&gt; vertex = reverseGraph.getVertex(stack.poll().getId());
            <span class="hljs-keyword">if</span>(visited.contains(vertex)){
                <span class="hljs-keyword">continue</span>;
            }
            Set&lt;Vertex&lt;Integer&gt;&gt; set = <span class="hljs-keyword">new</span> HashSet&lt;&gt;();
            DFSUtilForReverseGraph(vertex, visited, set);
            result.add(set);
        }
        <span class="hljs-keyword">return</span> result;
    }

    <span class="hljs-function"><span class="hljs-keyword">private</span> Graph&lt;Integer&gt; <span class="hljs-title">reverseGraph</span><span class="hljs-params">(Graph&lt;Integer&gt; graph)</span> </span>{
        Graph&lt;Integer&gt; reverseGraph = <span class="hljs-keyword">new</span> Graph&lt;&gt;(<span class="hljs-keyword">true</span>);
        <span class="hljs-keyword">for</span> (Edge&lt;Integer&gt; edge : graph.getAllEdges()) {
            reverseGraph.addEdge(edge.getVertex2().getId(), edge.getVertex1()
                    .getId(), edge.getWeight());
        }
        <span class="hljs-keyword">return</span> reverseGraph;
    }

    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">DFSUtil</span><span class="hljs-params">(Vertex&lt;Integer&gt; vertex,
            Set&lt;Vertex&lt;Integer&gt;&gt; visited, Deque&lt;Vertex&lt;Integer&gt;&gt; stack)</span> </span>{
        visited.add(vertex);
        <span class="hljs-keyword">for</span> (Vertex&lt;Integer&gt; v : vertex.getAdjacentVertexes()) {
            <span class="hljs-keyword">if</span> (visited.contains(v)) {
                <span class="hljs-keyword">continue</span>;
            }
            DFSUtil(v, visited, stack);
        }
        stack.offerFirst(vertex);
    }

    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">DFSUtilForReverseGraph</span><span class="hljs-params">(Vertex&lt;Integer&gt; vertex,
                                        Set&lt;Vertex&lt;Integer&gt;&gt; visited, Set&lt;Vertex&lt;Integer&gt;&gt; set)</span> </span>{
        visited.add(vertex);
        set.add(vertex);
        <span class="hljs-keyword">for</span> (Vertex&lt;Integer&gt; v : vertex.getAdjacentVertexes()) {
            <span class="hljs-keyword">if</span> (visited.contains(v)) {
                <span class="hljs-keyword">continue</span>;
            }
            DFSUtilForReverseGraph(v, visited, set);
        }
    }

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span></span>{
        Graph&lt;Integer&gt; graph = <span class="hljs-keyword">new</span> Graph&lt;&gt;(<span class="hljs-keyword">true</span>);
        graph.addEdge(<span class="hljs-number">0</span>, <span class="hljs-number">1</span>);
        graph.addEdge(<span class="hljs-number">1</span>, <span class="hljs-number">2</span>);
        graph.addEdge(<span class="hljs-number">2</span>, <span class="hljs-number">0</span>);
        graph.addEdge(<span class="hljs-number">1</span>, <span class="hljs-number">3</span>);
        graph.addEdge(<span class="hljs-number">3</span>, <span class="hljs-number">4</span>);
        graph.addEdge(<span class="hljs-number">4</span>, <span class="hljs-number">5</span>);
        graph.addEdge(<span class="hljs-number">5</span>, <span class="hljs-number">3</span>);
        graph.addEdge(<span class="hljs-number">5</span>, <span class="hljs-number">6</span>);

        StronglyConnectedComponent scc = <span class="hljs-keyword">new</span> StronglyConnectedComponent();
        List&lt;Set&lt;Vertex&lt;Integer&gt;&gt;&gt; result = scc.scc(graph);

        <span class="hljs-comment">//print the result</span>
        result.forEach(set -&gt; {
            set.forEach(v -&gt; System.out.print(v.getId() + <span class="hljs-string">" "</span>));
            System.out.println();
        });
    }
}
</div></code></pre>

    </body>
    </html>